#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct TreeNode
{
	int val;
	TreeNode *left;
	TreeNode *right;

	TreeNode() : val(0), left(nullptr), right(nullptr) {};
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {};
	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {};
};

typedef TreeNode Tree;

void print_tree(TreeNode *root)
{
	if (!root)
		return;
	cout << root->val << " ";
	print_tree(root->left);
	print_tree(root->right);
}

TreeNode *create_tree(const vector<int> &arr)
{
	if (arr.empty())
		return nullptr;

	TreeNode *root = new TreeNode(arr[0]);
	queue<TreeNode *> q;
	q.push(root);
	int i = 1;

	while (i < arr.size())
	{
		TreeNode *node = q.front();
		q.pop();

		if (arr[i] != INT_MIN)
		{ // use INT_MIN to represent null node
			node->left = new TreeNode(arr[i]);
			q.push(node->left);
		}
		i++;
		if (i >= arr.size())
			break;

		if (arr[i] != INT_MIN)
		{
			node->right = new TreeNode(arr[i]);
			q.push(node->right);
		}
		i++;
	}
	return root;
}

// int main() {
//	vector<int> arr = {1, 2, 3, INT_MIN, 4, 5, 6}; // INT_MIN 表示空节点
//	TreeNode* root = create_tree(arr);
//	print_tree(root);
// }
